We consider a uniform law of large numbers for random linear
maps: Let $M \in \mathbb{R}^{m \times n}$ be a random Gaussian matrix and let
$f: \mathbb{R} \rightarrow \mathbb{R}$ be $L$-Lipschitz. As $m$ increases, the average
of $\{ f ((Mx)_i) \}_{i \in [m]}$ converges to its expectation
uniformly over $x \in \mathbb{R}^n$. This concentration underlies several
algorithmic uses of random Gaussian maps, but their $O(mn)$
multiplication cost limits practicality. Recently, Cherapanamjeri and
Nelson (STOC’22) constructed a faster linear map with similar uniform
concentration but asymptotically slower convergence rate than
Gaussians. In this work, we give a new linear map that matches the
convergence rate of Gaussians while achieving an even faster runtime
than Cherapanamjeri-Nelson. As applications, we obtain improved
algorithms for $\ell_2 \rightarrow \ell_1$ embeddings, kernel
approximation, adaptive distance estimation, etc.
Based on joint work with Piotr Indyk.